The networks where connectivity is intermittent are characterized by the fact that many links suffer high loss rates, or even long propagation delays, so leading to the partitioning, subdividing of the network into a number of parts, within which the transmissions are good. Thus, the usual communication modes (for example, the TCP protocol, transport communication protocol) that rely on the existence of end-to-end paths, fail. The problem with the routing of the information is therefore to provide a method that enables a message to be routed from a source to a destination in this context. FIG. 1 shows an exemplary “connectivity chart” for the type of networks to which the inventive method applies. The nodes A, B, C, D and E in the chart represent the communicating entities and the bridge lines [A, B], [B, C], etc., correspond to the level of connectivity between the nodes. The higher the frequency of the dots of a bridge line, the fewer nodes are interconnected. On this chart, it can be seen that, whereas A and B are permanently connected, A and F are never connected and B and E are intermittently connected. A connectivity chart is, generally, represented by a parameter L, the width of the chart, a number n of nodes and the average degree of the chart D.
These networks are, for example, commonly referred to as delay tolerant networks (DTN). The DTNs are made up of entities or nodes, which communicate (communicate between themselves), and are mobile and wireless. These units are, for example, personal computers or personal data assistants (PDA), cell phones, sensors, etc. At any instant, communication is possible only between the nodes that are within radio range and, because of the very low level of connectivity, the probability that an end-to-end path (an existing and uninterrupted routing path) exists between two given entities is almost zero. Since data packets cannot be relayed using conventional IP (Internet Protocol) routing mechanisms, the relaying is then based on the store and forward principle. When an entity receives a message to be transmitted, it retains it until it encounters the recipient or else it transmits it opportunistically to a relay that can be selected according to a particular strategy.
Ad hoc networks to the emergency intervention services such as fire and police for example, or those used for military communications, can also change their communication mode in normal conditions (protocols of the MANET—mobile ad hoc networking—type, an autonomous system technology for mobile nodes) for a “disconnected” mode. The disconnections in these networks arise because of the mobility of the nodes, wireless-related problems, or the disappearance of nodes (lack of batteries, destruction, etc.). The invention described in this document can be applied in this context in order to maintain a “best effort” message routing service.
Various routing methods for this type of network are known from the prior art.
The documents by A. Lindgren, A. Doria, and O. Schelen, “Probabilistic routing in intermittently connected networks”, in Proc. SAPIR, 2004 and J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine, “MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks” in Proc. Infocom, 2006, describe routing methods based on probabilistic approaches. Such approaches are not based on the expectancy of the inter-contact times between the nodes. It is therefore difficult to estimate the delay to reach a destination. Furthermore, they have a more or less long term memory dependent on scale factors which are difficult to estimate.
In the document by S. Jain, K. Fall, and R. Prata, “Routing in a Delay Tolerant Network” in Proc. SigComm2004, the method calculates “the shortest paths” in a valued chart (chart in which weights are attributed to the bridge lines) with the average inter-contact delays between the nodes. This approach suffers from a lack of opportunism in the transmission possibilities that it implements and too strictly defines the sequence of the relays that must be used. Calculating the shortest paths by minimizing the sum of the delays of the bridge lines of the chart that are crossed does not lead to an efficient routing path.
In the document by V. Conan, J. Leguay, T. Friedman, “The heterogeneity of inter-contact time distributions: its importance for routing in delay tolerant networks”, arxiv:cs.NI/0609068, the “Spray and Wait” algorithm, introduced by M. Grossglauser and D. Tse, “Mobility increases the capacity of ad-hoc wireless networks”, Transactions on Networking, vol. 10 no. 4, pp. 477-486, August 2002, is applied. This makes it possible to deal only with the case of nodes that can be reached in two hops and not in any number of hops. The message delivery rate is, consequently, low and the delay longer than by implementing the inventive method. Furthermore, the optimization algorithm used to find the solution is exponential in time, so a sub-optimal solution is therefore proposed.
Despite the efficiency of the methods of the prior art, the latter do not make it possible to provide a routing method that minimizes the delivery delays on the scale of a whole network.
The object of the invention is based on the implementation of a multiple-hop method for transporting messages. The message can be relayed in succession by a number of nodes before reaching its destination.